package architect.algorithn;

import java.util.Scanner;

/**
 * 字符相似度
 *
 * @author guanxin
 * @date 2018/5/8 10:55
 */

public class CharacterSimilarity {
    static int[][] martix;

    static String str1 = "";
    static String str2 = "";

    public static void main(String[] args) {
        while (true) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入一个字符串：");
            str1 = scanner.nextLine();
            System.out.println("请输入另一个字符串：");
            str2 = scanner.nextLine();

            martix = new int[str1.length() + 1][str2.length() + 1];
            System.out.printf("字符串 %s 和 %s 的编辑距离为：%d \n", str1, str2, ld());
        }
    }

    // 编辑距离
    public static int ld() {
        //初始化边界值(忽略计算时的边界情况)
        for (int i = 0; i <= str1.length(); i++) {
            martix[i][0] = i;
        }

        for (int j = 0; j <= str2.length(); j++) {
            martix[0][j] = j;
        }

        //矩阵的 X 坐标
        for (int i = 1; i <= str1.length(); i++) {
            //矩阵的 Y 坐标
            for (int j = 1; j <= str2.length(); j++) {
                //相等情况
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    martix[i][j] = martix[i - 1][j - 1];
                } else {
                    //取“左前方”，“上方”，“左方“的最小值
                    int temp1 = Math.min(martix[i - 1][j], martix[i][j - 1]);

                    //获取最小值
                    int min = Math.min(temp1, martix[i - 1][j - 1]);

                    martix[i][j] = min + 1;
                }
            }
        }

        //返回字符串的编辑距离
        return martix[str1.length()][str2.length()];
    }
}
